We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of previous experiments, focusing on the setting where observational data is cheap (assumed infinite) and interventional data is expensive. While information greedy approaches are popular in active learning, we show that in this setting they can be exponentially suboptimal (in the number of interventions required), and instead propose an algorithm that exploits graph structure in the form of a centrality measure. If infinite interventional data is available, we show that the algorithm requires a number of interventions less than or equal to a factor of 2 times the minimum achievable number. We show that the algorithm and the associated theory can be adapted to the setting where each performed intervention yields finitely many samples. Several extensions are also presented, to the case where a specified set of nodes cannot be intervened on, to the case where $K$ interventions are scheduled at once, and to the fully adaptive case where each experiment yields only one sample. In the case of finite interventional data, through simulated experiments we show that our algorithms outperform different adaptive baseline algorithms.

The authors proposed a suite of algorithms for learning the structure of the causal graph under different assumptions (infinite and finite interventional sample, single vs. K intervention, non-manipulable variables). The assumption about the type of underlying causal graphs is quite stringent: a tree with no v-structure. Authors do not provide a compelling real-world example where this assumption makes sense. Nevertheless, this work seems to provide a theoretical insight to the very specific class of problems. Overall the paper is written clearly for readers to follow without any interruptions in general (there are some issues with how the paper is organized and I will talk about this below.)

As pointed out by the reviewers, these are the strengths and weaknesses of the paper: STRENGTHS The paper proposes algorithms for learning causal trees with intervention data under various assumptions, including infinite observational and interventional data, finite interventional data, allowing K interventions, and limiting the tree nodes that can be intervened on. There is a theoretical analysis on the bounds for the number of required interventions. The paper is overall clearly written. FOR IMPROVEMENT The main concern about this paper is the applicability of the proposed algorithms since they focus only on very specific type of causal graphs (causal trees with no v-structure). The authors should discuss the significance of being able to learn such graphs.

We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of previous experiments, focusing on the setting where observational data is cheap (assumed infinite) and interventional data is expensive. While information greedy approaches are popular in active learning, we show that in this setting they can be exponentially suboptimal (in the number of interventions required), and instead propose an algorithm that exploits graph structure in the form of a centrality measure. If infinite interventional data is available, we show that the algorithm requires a number of interventions less than or equal to a factor of 2 times the minimum achievable number. We show that the algorithm and the associated theory can be adapted to the setting where each performed intervention yields finitely many samples.

We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of previous experiments, focusing on the setting where observational data is cheap (assumed infinite) and interventional data is expensive. While information greedy approaches are popular in active learning, we show that in this setting they can be exponentially suboptimal (in the number of interventions required), and instead propose an algorithm that exploits graph structure in the form of a centrality measure. If infinite interventional data is available, we show that the algorithm requires a number of interventions less than or equal to a factor of 2 times the minimum achievable number. We show that the algorithm and the associated theory can be adapted to the setting where each performed intervention yields finitely many samples.